package baseclass.f_hash;

import java.util.HashMap;
import java.util.Map;

/**
 * @date 2020/2/29 15:45
 */
public class Code01_RandomPool<K>{
    Map<K,Integer> cache1 ;
    Map<Integer,K> cache2;
    private int index;//起始顺序
    public Code01_RandomPool() {
        cache1 = new HashMap<>();
        cache2 = new HashMap<>();
        index = 0;
    }


    public void add(K k){
        cache1.put(k,index);
        cache2.put(index,k);
        index ++;
    }
    public K getRandom(){
        if (index == 0) return null;
        //譬如放了5个数，索引是0-4，index现在是5，要产生0-4
        int random = (int) (Math.random()*index);
        return cache2.get(random);
    }
    public void remove(K k){
        if(!cache1.containsKey(k)) return;
        //先找map1中K的 index ， 譬如(c,2)
        int removeIndex = cache1.get(k);

        //将cache2中的最后一个譬如(25,z)的value拿出来，然后把(2,c)替换成(2,z)
        K lastValue = cache2.get(index-1);
        // 把2，c改为 2，z
        cache2.put(removeIndex,lastValue);
        //删除25，z
        cache2.remove(index-1);

        //把cache1中的z,25改为z,2 ,删除c,2
        cache1.remove(k);
        cache1.put(lastValue,removeIndex);
        index --;
    }
    public static void main(String[] args) {
        Code01_RandomPool<String> pool = new Code01_RandomPool<String>();
        pool.add("a");
        pool.add("b");
        pool.add("c");
        pool.add("d");
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println("==============");
        pool.remove("d");
        HashMap<String, Integer> map = new HashMap<>();
        //测试是否是等概率
        for (int i = 0; i < 100000000; i++) {
            String key = pool.getRandom();
            if (!map.containsKey(key)) {
                map.put(key, 1);
            } else {
                map.put(key, map.get(key) + 1);
            }
        }
        map.forEach((K,V)->{
            System.out.println(K+" "+V);
        });
    }
}
